/**
 * 优先级队列节点类
 */
class Node<T> {
  value: T;
  priority: number;
  next: Node<T> | null;

  constructor(value: T, priority: number) {
    this.value = value;
    this.priority = priority;
    this.next = null;
  }
}

/**
 * 用链表实现的优先级队列
 * 优先级值越大表示优先级越高
 */
export default class PriorityQueue<T> {
  private head: Node<T> | null;
  private size: number;

  public constructor() {
    this.head = null;
    this.size = 0;
  }

  /**
   * 将元素加入队列，按优先级排序
   * @param value 要加入队列的值
   * @param priority 优先级，值越大优先级越高
   */
  public add(value: T, priority: number): void {
    // 验证priority是有效数字
    if (typeof priority !== 'number' || isNaN(priority)) {
      throw new Error('优先级必须是有效的数字');
    }
    
    const newNode = new Node(value, priority);
    
    // 如果队列为空或新节点优先级高于头节点，则插入到队首
    if (!this.head || priority > this.head.priority) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 遍历链表找到合适的插入位置
      let current = this.head;
      // 继续移动直到找到优先级小于或等于新节点的位置（保持FIFO顺序）
      // 当新节点的优先级小于下一个节点的优先级时继续移动指针
      while (current.next && priority < current.next.priority) {
        current = current.next;
      }
      newNode.next = current.next;
      current.next = newNode;
    }
    
    this.size++;
  }

  /**
   * 移除并返回队列中优先级最高的元素
   * @returns 优先级最高的元素，如果队列为空则返回null
   */
  public pop(): T | null {
    if (!this.head) {
      return null;
    }
    
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    
    return value;
  }

  /**
   * 查看队列中优先级最高的元素但不移除
   * @returns 优先级最高的元素，如果队列为空则返回null
   */
  public peek(): T | null {
    if (!this.head) {
      return null;
    }
    
    return this.head.value;
  }

  /**
   * 检查队列是否为空
   * @returns 如果队列为空则返回true，否则返回false
   */
   public isEmpty(): boolean {
    return this.size === 0;
  }

  /**
   * 获取队列中元素的数量
   * @returns 队列中元素的数量
   */
   public getSize(): number {
    return this.size;
  }

  /**
   * 清空队列
   */
   public clear(): void {
    this.head = null;
    this.size = 0;
  }

  /**
   * 转换为数组
   * @returns 包含队列中所有元素的数组，按优先级排序
   */
   public toArray(): { value: T; priority: number }[] {
    const result: { value: T; priority: number }[] = [];
    let current = this.head;
    
    while (current) {
      result.push({ value: current.value, priority: current.priority });
      current = current.next;
    }
    
    return result;
  }

  /**
   * 移除指定值的元素
   * @param value 要移除的元素值
   * @param comparator 可选的比较函数，用于比较复杂对象
   * @returns 如果成功移除则返回true，否则返回false
   */
   public remove(value: T, comparator?: (a: T, b: T) => boolean): boolean {
    if (!this.head) {
      return false;
    }
    
    // 如果头节点是要移除的元素
    const isEqual = comparator ? comparator(this.head.value, value) : this.head.value === value;
    if (isEqual) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
    
    let current = this.head;
    while (current.next) {
      const nextEqual = comparator ? comparator(current.next.value, value) : current.next.value === value;
      if (nextEqual) {
        current.next = current.next.next;
        this.size--;
        return true;
      }
      current = current.next;
    }
    
    return false;
  }
}